program demo;

uses
  SysUtils, uTyp, uVar, uEng, uSpr, uInp, uFnt, uDrw, uSnd;

type
  TEng = class(uEng.TEng)
    procedure OnInit; override;
    procedure OnFrame; override;
    procedure OnStep; override;
  end;

  TMapNode = class(TListItem)
    parent: TMapNode;
    typ: Integer;
    x, y: Integer;
    f, g, h: Integer;
  end;

const
  MAP_WALL = 0;
  MAP_WAY = 1;
  MAP_START = 2;
  MAP_FINISH = 3;

  MAP_OFFS: array[0..7] of TPnt = (
    (x: -1; y:  0),
    (x: -1; y: -1),
    (x:  0; y: -1),
    (x:  1; y: -1),
    (x:  1; y:  0),
    (x:  1; y:  1),
    (x:  0; y:  1),
    (x: -1; y:  1)
  );

var
  map: array[0..7, 0..5] of TMapNode;
  open: TList;
  close: TList;
  start_, finish: TPnt;

procedure TEng.OnInit;
var
  i, j, k, x, y, newg: Integer;
  node: TMapNode;
begin
  res.AddFnt('fnt', 'fnt', 28, 300, 'Arial', 512, 512, FNT_EN, False);

  for j := 0 to 5 do
    for i := 0 to 7 do
    begin
      map[i,j] := TMapNode.Create;

      with map[i,j] do
      begin
        typ := MAP_WAY;
        x := i;
        y := j;
      end;
    end;

  start_ := MakePnt(3, 2);
  finish := MakePnt(6, 2);

  map[4,0].typ := MAP_WALL;
  map[4,1].typ := MAP_WALL;
  map[4,2].typ := MAP_WALL;
  map[4,3].typ := MAP_WALL;
  map[1,3].typ := MAP_WALL;
  map[2,3].typ := MAP_WALL;
  map[3,3].typ := MAP_WALL;
  map[1,2].typ := MAP_WALL;
  map[1,1].typ := MAP_WALL;

  map[start_.x, start_.y].typ := MAP_START;
  map[finish.x, finish.y].typ := MAP_FINISH;

  open := TList.Create;
  close := TList.Create;

  with map[start_.x, start_.y] do
  begin
    f := 0;
    g := 0;
    h := 0;
  end;

  node := map[start_.x, start_.y];
  k := 0;

  while True and (k < 3000) do
  begin
    open.Rem(node);
    close.Add(node);

    if (node.x = finish.x) and (node.y = finish.y) then Break;

    for i := 0 to 7 do
    begin
      x := node.x + MAP_OFFS[i].x;
      y := node.y + MAP_OFFS[i].y;

      if (x < 0) or (x > 7) or (y < 0) or (y > 5) then Continue;
      if map[x,y].typ = MAP_WALL then Continue;
      if close.Find(map[x,y]) <> -1 then Continue;

      if open.Find(map[x,y]) = -1 then
      begin
        with TMapNode(open.Add(map[x,y])) do
        begin
          parent := node;

          if i mod 2 = 0 then g := node.g + 10 else
            g := node.g + 14;

          h := (Abs(x - finish.x) + Abs(y - finish.y)) * 10;
          f := g + h;
        end;
      end else
      begin
        if i mod 2 = 0 then newg := node.g + 10 else newg := node.g + 14;

        if newg < map[x,y].g then
        begin
          map[x,y].parent := node.parent;
          
          with map[x,y] do
          begin
            g := newg;
            h := (Abs(x - finish.x) + Abs(y - finish.y)) * 10;
            f := g + h;
          end;
        end;
      end;
    end;

    node := nil;

    j := MaxInt;

    for i := 0 to open.size - 1 do
      if open.items[i] <> nil then
        if TMapNode(open.items[i]).f < j then
        begin
          node := TMapNode(open.items[i]);
          j := node.f;
        end;

    if node = nil then Exit;

    k := k + 1;
  end;
end;

procedure TEng.OnFrame;
var
  x, y: Integer;
  node: TMapNode;
begin
  for y := 0 to 5 do
    for x := 0 to 7 do
    begin
      case map[x,y].typ of
        MAP_WALL: drw.Rect(x * 40 + 40, y * 40 + 40, 40, 40, MakeClr($FF0000FF), DRW_FILL);
        MAP_WAY: drw.Rect(x * 40 + 40, y * 40 + 40, 40, 40, MakeClr($FF0000FF));
        MAP_START: drw.Rect(x * 40 + 40, y * 40 + 40, 40, 40, MakeClr($FF00FF00), DRW_FILL);
        MAP_FINISH: drw.Rect(x * 40 + 40, y * 40 + 40, 40, 40, MakeClr($FFFF0000), DRW_FILL);
      end;

      if open.Find(map[x,y]) <> -1 then drw.Rect(x * 40 + 40, y * 40 + 40, 40, 40, MakeClr($66FFFFFF), DRW_FILL);
      if close.Find(map[x,y]) <> -1 then
      begin
        drw.Circle(x * 40 + 60, y * 40 + 60, 5, 20, MakeClr($FFFF66FF), DRW_FILL);
        res.FindFnt('fnt').Draw(IntToStr(close.Find(map[x,y])), x * 40 + 72, y * 40 + 42, MakeClr($FFFFFF00));
      end;

      res.FindFnt('fnt').Draw(IntToStr(map[x,y].f), x * 40 + 42, y * 40 + 42, MakeClr($FFFFFFFF));
    end;

  node := map[finish.x, finish.y];

  while node.parent <> nil do
  begin
    drw.Rect(node.x * 40 + 40, node.y * 40 + 40, 40, 40, MakeClr($6600FF00), DRW_FILL);

    node := node.parent;
  end;
end;

procedure TEng.OnStep;
begin
  if inp.KeyDowned(KEY_ESCAPE) then eng.Stop;
  if inp.KeyPressed(KEY_P) then spr.FindDyn('dance').Play('dance');//snd.Find('s').FindBuf.Play;

  inp.Update;
end;

begin
  eng := TEng.Create;

  with eng.conf do
  begin
    w := 1024;
    h := 768;
    renderer := ENG_D3D8;
    player := ENG_DS;
  end;

  if eng.Init then
    eng.Start;

  eng.Free;
end.
